//
//  main.m
//  Interview
//
//  Created by lianglibao on 2019/2/26.
//  Copyright © 2019年 梁立保. All rights reserved.
//

#import <Foundation/Foundation.h>
#include <stdio.h>
#include  <stdlib.h>/*含malloc( ) 的头文件*/
struct node//①定义链表数据结构
{
	int num;
	struct node *next;
};
/********************构建单链表**********************/
/*返回的是与节点相同类型的指针*/
struct node *created(struct node *head) {
	struct node*p1, *p2;
	//③利用malloc ( )函数向系统申请分配一个节点
	p1 = p2 = (struct node*)malloc(sizeof(struct node));/*新节点*/
	printf("&p1= %p\n", &p1);
	scanf("%d",&p1->num); /*输入节点的值*/
	p1->next=NULL; /*将新节点的指针置为空*/
	
    /*输入节点的数值大于0*/
	while ( p1->num>0) {
		//④将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新
		//节点接到表尾;
		if(head==NULL) {
			head=p1;/*空表，接入表头*/
		} else {
			p2->next=p1;/*非空表，接到表尾*/
		}
		p2=p1;
		// p2 新p1
		p1 = (struct node*)malloc(sizeof(struct node));/*下一个新节点*/
		printf("&p2= %p\n", &p2);
		scanf("%d",&p1->num);/*输入节点的值*/
		//⑤判断一下是否有后续节点要接入链表，若有转到3 )，否则结束;
		if (p1->num <=0 ) {
			p1 = NULL;
			p2->next = NULL;
			break;
		}
	}
	printf("结束:p2->num=%d\n", p2->num);
	return head;/*返回链表的头指针*/
}
/********************构建单链表**********************/

/*出以head为头的链表各节点的值*/
void printLinkedList(struct node*head) {
	struct node *temp;
	temp=head;/*取得链表的头指针*/
	/*只要是非空表*/
	while(temp!=NULL) {
		printf("%d\n",temp->num);/*输出链表节点的值*/
		if (temp->next != NULL) {
			temp=temp->next;/*跟踪链表增长*/
		} else {
			temp = NULL;
			head = NULL;
			break;
		}
	}
}

// 1.单链表原地反转方式1
struct node *reverseList1(struct node *head) {
	if (head == NULL) return head;
	// 初始化tmp,当前初始值为-1
	struct node tmp = {-1, malloc(sizeof(struct node))};
	struct node *dummy = &tmp;
    //dummy -1, next 1...
    dummy->next = head;
    // prev 1, next 2...3...4...null
	struct node *prev = dummy->next;
    // pCur 2, next 3...4...null
	struct node *pCur = prev->next;
	while (pCur != NULL) {
        // prev 1, next 3...4...null
        // prev 1, next 4...null
        // prev 1, next ...null
		prev->next = pCur->next;
        
        // pCur 2, next 1...3...4...null
        // pCur 3, next 2...1...4...null
        // pCur 4, next 3...2...1...null
		pCur->next = dummy->next;// (取得就是prev)
        
        //dummy -1, next 2...1...3...4...null
        //dummy -1, next 3...2...1...4...null
        //dummy -1, next 4...3...2...1...null
		dummy->next = pCur;// (最后在这里赋值完成最终反转)
        
        // pCur 3, next 4...null
        // pCur 4, next...null
        // pCur ...null
		pCur = prev->next;
	}
	return dummy->next;
}

// 2.新建链表,头节点插入法,有bug!!
struct node *reverseList2(struct node *head) {
	struct node *dummy = &((struct node){-1, malloc(sizeof(struct node))});
	struct node *pCur = head;
	while (pCur != NULL) {
		struct node *pNex = pCur->next;
		pCur->next = dummy->next;
		dummy->next = pCur;
		pCur = pNex;
	}
	return dummy->next;
}


int main(int argc, const char * argv[]) {
	@autoreleasepool {
		struct node *head;
		head = NULL; //②建一个空表
		head = created(head);/*创建单链表*/
		printLinkedList(head); /*打印单链表*/
		printf("--------原地反转之后---------\n");
		printLinkedList(reverseList1(head));
//		printf("-----------------\n");
//		printLinkedList(reverseList2(head));
	}
	return 0;
}



